package datastructure;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Author leecho
 * @Date: 2021/10/13 14:01
 * @Version 1.0
 */


/*
* 思路：
* 获取到用户输入的中缀表达式
* - 字符串形式，中间没有空格
*
* 把接收到中缀表达式字符串转换为数组
* - 创建一个ArrayList
* - 依次遍历然后添加
*
* 把中缀表达式转换为后缀表达式
* - 扫描，如果是数字直接加入
* - 扫描，如果不是数字是符号，进行判断
*   - 如果当前符号栈为空，则直接加入
*   - 如果当前符号栈不为空，则进行判断
*       - 如果是 （ 则直接加入
*       - 如果不是括号是符号则和现在符号栈中的栈顶符号进行比较
*           - 如果小于则就将符号栈的栈顶的符号压入数据栈中，然后再将扫描到的符号压入符号栈中
*           - 如果大于，则直接把扫描到的符号压入数据栈中
*       - 如果是 ）则把现在符号栈中栈顶的符号直接压入数据栈中
* - 最后把符号栈中的所有符号依次加入数据栈中
*
*
* */
public class InfixToSuffix {
    public static void main(String[] args) {
        String fh = "1+((2+3)*4)-5";
        List<String> strings = stringList(fh);

        List<String> list = infixToSuffix(strings);

        System.out.println(strings);

        System.out.println(list);
    }

    public static List<String> stringList(String s){
        ArrayList<String> list = new ArrayList<>();
        int i = 0;
        char c = ' ';
        String str;

        do {
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57){
                list.add("" + c);
                i++;
            } else {
                str = "";
                if ((c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57){
                    str += c;
                    i++;
                }
                list.add(str);
            }
        } while (i < s.length());
        return list;
    }

    public static List<String> infixToSuffix(List<String> list){
        Stack<String> s1 = new Stack<>();
        ArrayList<String> a1 = new ArrayList<>();

        for (String s : list) {
            if (s.matches("\\d+")){
                a1.add(s);
            } else if (s.equals("(")){
                s1.push(s);
            } else if (s.equals(")")){
                while (!s1.peek().equals("(")){
                    a1.add(s1.pop());
                }
                s1.pop();
            } else {
                if (s1.empty() || s1.peek().equals("(")){
                    s1.push(s);
                } else if (compare(s) > compare(s1.peek())) {
                    a1.add(s);
                } else if (compare(s) <= compare(s1.peek())){
                    a1.add(s1.pop());
                    s1.push(s);
                }
            }
        }
        while (!s1.empty()){
            a1.add(s1.pop());
        }
        return a1;
    }

    public static int compare(String c){
        if (c.equals("+") || c.equals("-"))
            return 1;
        else if (c.equals("*") || c.equals("/"))
            return 2;
        return -1;
    }
}


